package com.zrf.base.knowledge.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * //数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * //
 * //
 * //
 * // 示例：
 * //
 * // 输入：n = 3
 * //输出：[
 * //       "((()))",
 * //       "(()())",
 * //       "(())()",
 * //       "()(())",
 * //       "()()()"
 * //     ]
 * //
 * // Related Topics 字符串 回溯算法
 * // 👍 1381 👎 0
 *
 * @author zhouruifeng
 * @date 2020-10-24 19:31:46
 */
public class GenerateParentheses {
    public static void main(String[] args) {
        Solution solution = new GenerateParentheses().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> resultList = new ArrayList<>();
            generate(resultList, new StringBuilder(), 0, 0, n);
            return resultList;
        }

        private void generate(List<String> resultList, StringBuilder current, Integer open, Integer close, Integer n) {
            if (current.length() == n * 2) {
                resultList.add(current.toString());
                return;
            }

            if (open < n) {
                current.append("(");
                generate(resultList, current, open + 1, close, n);
                current.deleteCharAt(current.length() - 1);
            }
            if (open > close) {
                current.append(")");
                generate(resultList, current, open, close + 1, n);
                current.deleteCharAt(current.length() - 1);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}